package com.pandawhale.algorithm.tree;

public class Tree {

    //二叉树
    //满二叉树
    //完全二叉树
    //二叉排序树
    //二叉平衡树
    //二叉平衡排序树

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public static Node create(int value) {
            Node node = new Node();
            node.value = value;
            node.left = null;
            node.right = null;
            return node;
        }

    }


    public static void main(String[] args) {
//        int[] arr = {4,1,9,6,2,8,5};
//        Node root = Node.create(arr[0]);
//        for (int i = 1 ; i < arr.length ; i ++) {
//            Node node = Node.create(arr[i]);
//            constructTree(root, node);
//        }
        int[] pre = {4,1,2,9,6,5,8};
        int[] mid = {1,2,4,5,6,8,9};
        Node root = buildTree(pre, mid);
        printTree(root);
    }

    public static void constructTree(Node root, Node node) {
        if (root.value > node.value) {
            if (root.left == null) root.left = node;
            else constructTree(root.left, node);
        }
        if (root.value < node.value) {
            if (root.right == null) root.right = node;
            else constructTree(root.right, node);
        }
    }

    //中序遍历（前序、后序）
    public static void printTree(Node root) {
        if (root == null) return;
        printTree(root.left);
        System.out.println(root.value);
        printTree(root.right);
    }

    //前序遍历
    public static boolean search(Node root, int value) {
        if (root == null) return false;
        if (root.value == value) return true;
        return search(root.left, value) || search(root.right, value);
    }

    //保存二叉树
    //存储 中序遍历 + 前序遍历 或者 中序遍历 + 后序遍历
    public static Node buildTree(int[] pre, int[] mid) {
        //找根
        return buildTree(pre, 0, pre.length, mid, 0, mid.length);
    }

    public static Node buildTree(int[] pre, int preLeft, int preRight, int[] mid, int midLeft, int midRight) {
        //找根
        Node root = Node.create(pre[preLeft]);
        if (preRight - preLeft == 1) return root;
        int midRootIndex = find(mid, midLeft, midRight, root.value);
        //找左
        int leftLen = midRootIndex - midLeft;//长度
        if (leftLen == 0) root.left = null;
        else root.left = buildTree(pre, preLeft + 1, preLeft + 1 + leftLen, mid, midLeft, midRootIndex);
        //找右
        if (midRight - midRootIndex == 1) root.right = null;
        else root.right = buildTree(pre, preLeft + leftLen + 1, preRight, mid, midRootIndex + 1, midRight);
        return root;
    }

    private static int find(int[] arr, int begin, int end, int value) {
        for (int i = begin ; i < end ; i ++) {
            if (arr[i] == value) return i;
        }
        return -1;
    }
 }







